//给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//
//
//L0 → L1 → … → Ln - 1 → Ln
//
//
// 请将其重新排列后变为：
//
//
//L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
//
// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
//
//
//
// 示例 1：
//
//
//
//
//输入：head = [1,2,3,4]
//输出：[1,4,2,3]
//
// 示例 2：
//
//
//
//
//输入：head = [1,2,3,4,5]
//输出：[1,5,2,4,3]
//
//
//
// 提示：
//
//
// 链表的长度范围为 [1, 5 * 10⁴]
// 1 <= node.val <= 1000
//
//
// Related Topics 栈 递归 链表 双指针 👍 1189 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 Do not return anything, modify head in-place instead.
 */
function reorderList(head: ListNode | null): void {
    if (head === null || head.next === null) return;
    let fastNode: ListNode = head,
        slowNode: ListNode = head;
    while (fastNode.next !== null && fastNode.next.next !== null) {
        slowNode = slowNode.next!;
        fastNode = fastNode.next.next;
    }
    let head1: ListNode | null = head;
    // 反转后半部分链表
    let head2: ListNode | null = reverseList(slowNode.next);
    // 分割链表
    slowNode.next = null;
    /**
     直接在head1链表上进行插入
     head1 链表长度一定大于或等于head2,
     因此在下面的循环中，只要head2不为null, head1 一定不为null
     */
    while (head2 !== null) {
        const tempNode1: ListNode | null = head1!.next,
            tempNode2: ListNode | null = head2.next;
        head1!.next = head2;
        head2.next = tempNode1;
        head1 = tempNode1;
        head2 = tempNode2;
    }
};
function reverseList(head: ListNode | null): ListNode | null {
    let curNode: ListNode | null = head,
        preNode: ListNode | null = null;
    while (curNode !== null) {
        const tempNode: ListNode | null = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    return preNode;
}
//leetcode submit region end(Prohibit modification and deletion)
